Khu vực thành phố Jeju đã đóng vai trò là trung tâm của hòn đảo từ thời kỳ trước khi có những ghi chép. Tam Tính Huyệt, các vệ trũng mà được cho là từ đó ba tổ tiên của người dân Jeju đã đến, nằm tại thành phố Jeju.

Thành phố phát triển nhanh chóng từ thập niên 1970. Shin Jeju (신제주), hay "Tân Jeju", được hình thành trong một vài thập kỉ trước đây, trên ngọn đồi từ sân bay với nhiều tòa nhà chính quyền. Các tòa nhà lợp rạ từng thông dụng tại thành phố cho đến những năm 1970 nay đã dần biến mất.

Thành phố được tách ra từ huyện Bukjeju vào năm 1955. Tuy nhiên vào năm 2005 cử tri tỉnh Jeju đã tán thành đề xuất hợp nhất thành phố với huyện Bukjeju, cùng như sáp nhập Seogwipo với huyện Namjeju để hình thành hai thành phố lớn do tỉnh quản lý. Thay đổi hành chính này có hiệu lực từ tháng 7 năm 2006.